\chapter{Predefined Types and Classes} \label{types}

The \frege{} Prelude contains predefined classes, types and functions that are implicitly imported into every \frege{} program. In this chapter, we describe the types and classes found in the Prelude. Most functions
are not described in detail here.


\section{Standard \frege{} Types}

These types are defined by the \frege{} Prelude. Numeric types are described in \autoref{numeric}. When appropriate,
the \frege{} definition of the type is given. Some definitions may not be completely valid on syntactic
grounds but they faithfully convey the meaning of the underlying type.


\subsection{Booleans} \index{standard types!Bool} \label{boolean}

\begin{code}
data Bool = pure native boolean
\end{code}

The boolean type \texttt{Bool} is the primitive \java{} type \texttt{boolean}. 
The boolean values are represented by two keywords, \texttt{false} and \texttt{true}, see also \autoref{boolliteral}.

Basic boolean functions are \texttt{\&\&} (and), \texttt{||} (or), and \term{not}. 
The unary operator \texttt{!} is an alias for \term{not}. 
These operations are implemented in such a way that the corresponding \java{} operator is employed.
This could promote unwanted strictness from the second operands of \texttt{\&\&} and \texttt{||}. For such cases, functions \texttt{und} and \texttt{oder} are provided that are lazy in their second operands.

The name \texttt{otherwise} is defined as \texttt{true} to make guarded expressions more readable.

\texttt{Bool} has instances for \texttt{Show}, \texttt{Eq}, \texttt{Ord}, \texttt{Enum} and \texttt{Bounded}.

\hasdiff{The constructors \texttt{True} and \texttt{False} do not exist.}


\subsection{Characters} \index{standard types!Char} \index{character!type}

\begin{code}
data Char = pure native char
\end{code}

The character type \texttt{Char} is the primitive \java{} type \texttt{char}, 
whose values, according to the Java Language Specification are 
\emph{16-bit unsigned integers representing UTF-16 code units}.
The lexical syntax for characters is defined in \autoref{charliteral}; 
character literals denote values of type \texttt{Char}.
Type \texttt{Char} is an instance of the classes \texttt{Show}, \texttt{Eq}, \texttt{Ord}, \texttt{Enum} and \texttt{Bounded}.


\subsection{Strings} \index{standard types!String}

\begin{code}
data String = pure native java.lang.String
\end{code}

The type \texttt{String} is the \java{} type \texttt{java.lang.String}.
For most \texttt{java} methods that work on strings, there is a corresponding native function binding.

\texttt{String} is an instance of the classes 
\texttt{Show}, \texttt{Eq}, \texttt{Ord}, \texttt{Empty}, \texttt{ListLike} and \texttt{ListSource}. 
The latter one allows string values to stand on the right side of the arrow in list comprehension generators, 
thus providing silent conversion to list of characters.

Further operations are explicit conversion to and from list of characters with \texttt{unpacked} and \texttt{packed}, 
conversion to various numeric types and access to individual characters of a string with integer indexes.

\hasdiff{Strings are not list of characters, though conversion functions to and from lists exist.}

\subsection{Predefined Algebraic Data Types} \index{standard types!algebraic}


\subsubsection{Lists} \label{listtype} \index{list} \index{standard types!algebraic!list}

\begin{code}
data [a] = [] | a : [a]    -- this syntax is not really allowed
\end{code}

Lists are an algebraic data type of two constructors, although with special syntactic support, as described in \autoref{listterm}.
The first constructor is the null list, written [] ("nil"), and the second is \sym{:} ("cons"). The module \texttt{frege.prelude.PreludeList}, whose definitions are automatically imported in every \frege{} program unless prevented by the user, defines many standard list functions.

Lists are an instance of classes \texttt{Show}, \texttt{Eq}, \texttt{Ord}, \texttt{Empty}, \texttt{ListLike}, \texttt{ListSource}, \texttt{Monad} and \texttt{Functor}.


\subsubsection{Tuples} \label{tupletypes} \index{tuples} \index{standard types!algebraic!tuples}

The tuple types are convenient product types for grouping a fixed number of  values that can have different types. Tuple types with 2 to 26 components are predefined. Special syntactic support for tuples is described in \autoref{tupleterm}.

The following functions are defined for pairs (2-tuples): \texttt{fst}, \texttt{snd}, \texttt{curry}, and \texttt{uncurry}. Similar functions are not predefined for larger tuple.

The Prelude provides instances for classes \texttt{Show}, \texttt{Eq}, \texttt{Ord} and \texttt{Bounded} for pairs and 3-tuples. 
Instances of the same classes for tuple sizes 4 to 7 are predefined in package \texttt{frege.data.Tuples}.

The \texttt{zip}/\texttt{unzip} family of functions is also available by default for tuples of size 2 and 3. 
The package \texttt{frege.data.List} makes them available for tuples up to size 7.


\subsubsection{The Unit Datatype} \label{unittype} \index{standard types!algebraic!unit}
\begin{code}
data () = ()    -- pseudo syntax
\end{code}

The unit type $()$ is an enumeration with just one constant, which is also named $()$. 
The unit type is often the result type of impure functions that exist for their side effects.


\subsection{Function Types}

Functions are an abstract type: no constructors directly create functional values.
The following simple functions are found in the Prelude: \texttt{id}, \texttt{const}, \texttt{(.)}, \texttt{flip}, \texttt{(\$)}.

\subsection{ST, IO and RealWorld}

\begin{code}
abstract data ST s a = ST (s -> a)
    where  run :: forall a. (forall s.ST s a) -> a
abstract data RealWorld = RealWorld
type IO = ST RealWorld 
\end{code}

The abstract \texttt{ST} type encapsulates impure operations, for an in depth discussion see \cite{lazyst}.

In short, it is possible to model program actions that are impure only locally, but can be regarded as overall pure. For example, an array could be built from a list, and then computations  that need fast indexing could be performed. Once the result is computed, the array would be gone and garbage collected.

Such computations can be performed with the help of the \texttt{ST.run} function. Note the higher rank polymorphic type of that function, which not only prevents execution for \texttt{ST} actions that are not polymorphic in the type argument $s$, but also escape of impure values that have the $s$ in their type.

The very same mechanism is used for input/output. Functions with return type \texttt{IO a} produce \texttt{ST RealWorld a} values that can \textbf{not} be run with \texttt{ST.run}.


\subsection{Exceptions}


\frege{} uses the \java{} exception facilities to model undefined or erroneous behavior.

The function \texttt{error}, when applied to a string and evaluated, 
constructs and throws such exceptions. Pattern matches and pattern guards
can fail to match, the compiler adds code that raises exceptions in such cases.

Likewise, exceptions can be thrown in pure native code. 
It is possible, and, in the case of so called 
\emph{checked exceptions}\footnote{see \cite[§11.2]{langspec3}}
unavoidable to catch such exceptions and return them instead of the expected result.

Last but not least, the \java{} virtual machine can throw exceptions. 

Exceptions can be catched, raised and acted upon in ST actions,
including native impure code. 

There is support for creating custom frege exception types. \inmargin{not yet implemented}


\subsection{Other Types}

\begin{code}
data Maybe a = Nothing | Just a
derive Eq (Maybe a); derive Ord (Maybe a); derive Show (Maybe a)

data Either a b = Left a | Right b
derive Eq (Either a b); derive Ord (Either a b);
derive Show (Either a b)

data Ordering = Lt | Eq | Gt
derive Enum Ordering
derive Show Ordering
\end{code}

The type \texttt{Ordering} is used by \sym{(<=>)} in class \texttt{Ord}.
The Prelude provides functions \texttt{maybe} and \texttt{either}.

An alternate syntax is supported for nested \texttt{Either} types. \label{nested-either}

\begin{code}
type (a|b) = Either a b
type (a|b|c) = Either (Either a b) c
type (a|b|c|....|z) = Either (Either (Either (Either ...))) z
\end{code}

The \sym{|} is left associative, and acts like an infix \texttt{Either} type constructor.
Hence the type 
\texttt{($t_1$|$t_2$|$t_3$)} is the same as 
\texttt{Either (Either $t_1$ $t_2$) $t_3$}.

Note that a nested Either type must appear in parentheses, 
but inside the outer pair of parentheses arbitrary many \texttt{Either} alternatives can be written.

A value $v$ of the above type could be deconstructed most easily with the \texttt{either} function like
\example{\tt
($f_a$ ` either` $f_b$ ` either` $f_c$) $v$
}
where the infix \texttt{either} operators correspond to the \sym{|} type constructors, 
and the positions of the $f_i$ correspond to the values of type $t_i$.


\section{Standard \frege{} Classes} \label{std-classes} \index{standard classes}

\todo{To be written later.}


\section{Numbers} \label{numeric} \index{standard types!numeric}

\todo{To be written later.}